#include <iostream>
#include <map>
#include <iterator>

using namespace std;


int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		map<int,int> mp;
		for(int i = 0; i < n; ++i){
			int num;
			cin >> num;
			mp[num]++;
		}
		for(auto it = mp.rbegin(); it != mp.rend();){
			auto pre = next(it);
			if(pre != mp.rend()){
				if(pre->first + 1 == it->first){
					mp[pre->first] += mp[it->first];
					auto temp = it.base();
					--temp;
					temp = mp.erase(temp);
					it = map<int, int>::reverse_iterator(temp);
				}else{
					++it;
				}
			}else{
				break;
			}
		}
			
		/*	
		for(auto it = mp.rbegin(); it != mp.rend(); ++it){
			cout << it->first << "===" << it->second << endl;
		}
		*/
		
		while(mp.size() != 1){
			auto it = ++mp.rbegin();
			for(; it != mp.rend(); ++it){
//				cout << it->first << "===" << it->second;
				if(it->second > 1){
					break;
				}
			}
			if(it != mp.rend()){
				auto nt = prev(it);
				int key = (it->first + nt->first)/2;
				mp[key] += 2;
				--it->second;
				if(!it->second){
					auto temp = it.base();
					--temp;
					mp.erase(temp);
				}
				--nt->second;
				if(!nt->second){
					auto temp = nt.base();
					--temp;
					mp.erase(temp);
				}
				if(mp.count(key+1)){
					mp[key] += mp[key+1];
					mp.erase(key+1);
				}
				if(mp.count(key-1)){
					mp[key-1] += mp[key];
					mp.erase(key);
				}
			}else{
				auto it2 = ++mp.rbegin();
				auto pre = next(it2);
				if(pre != mp.rend()){
					int key = (it2->first + pre->first)/2;
					mp[key] += 2;
					mp.erase(it2->first);
					mp.erase(pre->first);
				}else{
					int key = (it2->first + mp.rbegin()->first)/2;
					mp[key] += 2;
					--it2->second;
					if(!it2->second){
						auto temp = it2.base();
						--temp;
						mp.erase(temp);
					}
					--mp.rbegin()->second;
					if(!mp.rbegin()->second){
						auto temp = mp.rbegin().base();
						--temp;
						mp.erase(temp);
					}
					if(mp.count(key+1)){
						mp[key] += mp[key+1];
						mp.erase(key+1);
					}
					if(mp.count(key-1)){
						mp[key-1] += mp[key];
						mp.erase(key);
					}
				}
			}
		}
		cout << mp.begin()->first;
		if(t) cout << endl;
	}

	return 0;
}

